package exercises.leetcode;

import exercises.leetcode.utils.ToArray;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * <a href="">
 * </a>
 *
 * <p><span color="#87CEEB">描述:</span>
 *
 * @author or2
 * @date 2021年10月30日 时间: 22:46
 */
public class No5899 {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (o1, o2) -> {
            int off = o1[1] - o2[1];
            if (off != 0) return off;
            else return o1[0] - o2[0] == 0 ? o1[2] - o2[2] : o1[0] - o2[0];
        });
        int length = events.length;
        var dp = new TreeMap<Integer, Integer>();
        int res = 0;
        for (int[] event : events) {
            int end = event[1], start = event[0], val = event[2];
            var pre = dp.lowerEntry(start);
            int preVal = pre == null ? 0 : pre.getValue();
            int curVal = preVal + val;
            if (curVal > res) res = curVal;
            var preEnd = dp.lowerEntry(end);
            int endVal = preEnd == null ? 0 : preEnd.getValue();
            if (val > endVal)
                dp.put(end, val);
        }

        return res;
    }

//    public int maxTwoEvents2(int[][] events) {
//        Arrays.sort(events, (o1, o2) -> {
//            int off = o1[1] - o2[1];
//            if (off != 0) return off;
//            else return o1[0] - o2[0] == 0 ? o1[2] - o2[2] : o1[0] - o2[0];
//        });
//        int length = events.length;
//        var dp = new int[events[length - 1][1] + 2];
//        int res = 0;
//        for (int[] event : events) {
//            int end = event[1], start = event[0], val = event[2];
//            int curVal = dp[start - 1] + val;
//            if (curVal > res) res = curVal;
//            if (val > dp[end])
//                Arrays.fill(dp, end, dp.length, val);
//        }
//
//        return res;
//    }

    public static void main(String[] args) {
//        int[][] events = ToArray.toInt2Array("[[10,83,53],[63,87,45],[97,100,32],[51,61,16]]");
        int[][] events = ToArray.toInt2Array("[[1,3,2],[4,5,2],[2,4,3]]");
        No5899 no5899 = new No5899();
        System.out.println(no5899.maxTwoEvents(events));
    }
}
